import com.sun.xml.internal.bind.v2.model.annotation.Quick;

import java.util.Arrays;
import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2023-07-29
 * Time: 19:55
 */
public class QuickSort {

    /**
     * 快速排序
     * 时间复杂度 : O(N * logN) 类似二叉树, 分治数组的每一层元素都有 N 个, 而一共分治有 log N 层, 也就是树的高度
     * 空间复杂度 : O(logN) 当左边开辟 logN 空间后, 排序结束回收, 右边紧接着开辟 logN 空间大小
     * 稳定性 : 不稳定排序
     * TODO : 当给定排序数组是有序时, 时间复杂度为 O(N ^ 2), 同时空间复杂度退化为 O(N), 相当于没有左树或者右树的链表
     *
     * @param array 排序数组
     * @param start 需要排序的数组起始位置
     * @param end   需要排序的数组结束位置
     */
    public void quickSort(int[] array, int start, int end) {
        // 大于等于的时候, 表明分治的数组只有一个元素, 不需要在划分进行排序了
        // TODO : 当给定需要排序的数组为 1 2 3 4 5 时, 此时找到基准 pivot 在 0 位置, 然后递归其左边, 结束位置 end 为 pivot - 1
        //        此时如果没有 > 条件限制, 会继续向下排序, 导致越界
        if (start >= end) {
            return;
        }

        // 由于数组过大情况下, 分治分组采用递归主要都集中在后面几层, 因此小区间内可以采用插入排序提升效率
        if (end - start + 1 <= 7) {
            insertSort(array, start, end);
        }

        System.out.println("start :" + start + " end : " + end);
        // TODO : 在进行分治划分数组之前, 提前去调整初始基准元素, 让其初始划分时划分均匀
        int index = findMidOfThreeNum(array, start, end);

        // 将提前调整的初始基准元素放到数组开头, 便于后续划分的数组中 left 作为基准元素
        swap(array, start, index);

        // 获取排序数组的基准元素
        int pivot = partitionHoare(array, start, end);


        // 递归排基准的左边
        quickSort(array, start, pivot - 1);

        // 递归排基准的右边
        quickSort(array, pivot + 1, end);
    }

    /**
     * 对指定区间进行插入排序
     *
     * @param array 传入的小数组
     * @param left  数组左边界
     * @param right 数组右边界
     */
    public void insertSort(int[] array, int left, int right) {
        // 分治后传入的数组, left 已经有序了不需要再排了, 因此从 left + 1 开始
        // 同时, 传入的 end 实际上是下标, 因此要取 i <= right
        for (int i = left + 1; i <= right; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= left; j--) {
                // j 和后一个元素 tmp 进行比较
                // array[j] > tmp
                if (array[j] > tmp) {
                    // 调整位置 小的放到前面
                    array[j + 1] = array[j];

                } else {
                    // 前一个比当前小, 不再需要重新排序放回原位置
                    // array[j + 1] = tmp;
                    // 前面有序的前一个最大的数都比当前这个数小, 说明此时无需再排序
                    break;
                }
            }

            // 走到此时, 如果最后一个数最小, 那么 j 一定会回退到 -1 下标处
            array[j + 1] = tmp;
        }
    }

    /**
     * TODO : 当排序的数组太大, 会导致堆溢出, 同时当排序数组有序的时候, 快排时间复杂度会最大 O(N ^ 2) , 并且空间复杂度也会改变 O(N)
     *        那么, 如何解决这个问题 ? 有序时如何将这个数组均分让其使用分治思想划分数组时, 不会只变成没有左数组或者右数组的情况.
     *        其时间复杂度较好情况就是均分, 类似于二分
     */

    public int findMidOfThreeNum(int[] array, int start, int end) {
        int midIndex = start + ((end - start) >> 1); // 防止数组过大导致中间值直接求和除 2 越界.

        if (array[start] < array[end]) {
            // 3  X   9
            if (array[midIndex] < array[start]) {
                return start;
            } else if (array[midIndex] > array[end]) {
                return end;
            } else {
                return midIndex;
            }

        }
        // 9  X   3
        else {
            if (array[midIndex] > array[start]) {
                return start;
            } else if (array[midIndex] < array[end]) {
                return end;
            } else {
                return midIndex;
            }
        }
    }


    /**
     * 分治思想 - 将大的数组以基准元素划分成左右两部分
     * 霍尔法寻找基准元素
     *
     * @param array 划分的数组
     * @param left  子数组的左边界
     * @param right 子数组的右边界
     */
    public int partitionHoare(int[] array, int left, int right) {

        // 以第一个数组第一个元素的下标为起始基准, 并记录
        int i = left;

        int pivot = array[left];
        // 在分组的边界内从两端向中间寻找
        while (left < right) {
            // left < right 条件限制 1 2 3 4 5 这样的数组最终 right-- 会越界
            // TODO : 为什么从 right 开始寻找, 而不是从 left 开始寻找呢 ?
            //        原因在于当 pivot 以 left 为基准时, 如果从 left 开始寻找, left 和 right 相遇后
            //        该元素会比 pivot 基准元素大, 最后被交换到了 left 无法分成基准左边都比基准小, 右边都比基准大
            while (left < right && array[right] >= pivot) {
                // 右边找大于 pivot 的
                right--;
            }

            // TODO : 为什么两个 while 条件中要有等于号 ?
            //        如果没有等于号, 基准元素和 right 右边寻找时遇到相同元素, left 和 right 在之后都不会动, 会出现死循环.
            while (left < right && array[left] <= pivot) {
                // 左边找小于 pivot 的
                left++;
            }

            // 此时 right 下标的值笔 pivot 小, left 下标的值笔 pivot 大
            // 交换
            swap(array, left, right);
        }

        // 最终将起始下标基准对应元素交换到 left 位置, 后续则
        swap(array, left, i);

        // 返回新基准下标
        return left; // 相遇时停止, 因此 right 也行
    }

    /**
     * 挖坑法实现快排 -- 挖坑发寻找基准元素
     *
     * @param array 排序的数组
     * @param left  数组左边界
     * @param right 数组右边界
     * @return 返回基准元素下标
     */
    public int partitionDigHole(int[] array, int left, int right) {
        // 选择初始 left 元素为坑位元素, 此时 left 相当于空出一个坑等着填
        int pivot = array[left];
        while (left < right) {
            // 从右边开始寻找, 寻找到一个小于 pivot 基准的数
            while (left < right && array[right] >= pivot) {
                right--;
            }

            // 右边找到小于 pivot 的元素以后, 填入到当前的坑位
            array[left] = array[right];

            // 接着从左边寻找, 寻找一个大于 pivot 基准的数
            while (left < right && array[left] <= pivot) {
                left++;
            }

            // 左边寻找到大于 pivot 的元素以后, 填入到当前坑位
            array[right] = array[left];
        }

        // left 和 right 相等后, 将原本选出的初始坑位值放回到当前坑位中完成填坑
        array[left] = pivot;

        // 返回基准元素下标
        return left;
    }


    /**
     * 前后双指针法实现快排 -- 双指针寻找基准元素下标
     *
     * @param array 排序的数组
     * @param left  数组的左边界
     * @param right 数组的有边界
     * @return 返回基准元素下标
     */
    public int partitionDoublePointer(int[] array, int left, int right) {
        int prev = left; // 寻找小于基准元素
        int cur = left + 1; // 寻找大于基准元素

        // 等同于从右边开始寻找, 当 cur 遍历结束则结束
        while (cur <= right) {
            if (array[cur] < array[left] && array[++prev] != array[left]) {
                swap(array, cur, prev);
            }
            cur++;
        }

        // 将 prev 位置元素和 left 位置元素交换
        swap(array, prev, left);

        // 返回新基准下标
        return prev;
    }

    /**
     * 实现数组中两个元素的交换
     *
     * @param array 原排序数组
     * @param left  交换的下标
     * @param right 交换的下标
     */
    public void swap(int[] array, int left, int right) {
        int tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }

    public static void main(String[] args) {
        Random random = new Random();
        QuickSort quickSort = new QuickSort();
        int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

//        quickSort.quickSort(array, 0, array.length- 1);
//        System.out.println(Arrays.toString(array));

        int[] arr = new int[10_00000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt();
        }

        int[] arr2 = {
                1, 2, 3, 4, 5, 6, 7, 8, 9, 10
                , 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
                , 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
                , 31, 32, 33, 34, 35, 36, 37, 38, 39, 40
                , 41, 42, 43, 44, 45, 46, 47, 48, 49, 50
                , 51, 52, 53, 54, 55, 56, 57, 58, 59, 60
                , 61, 62, 63, 64, 65, 66, 67, 68, 69, 70
                , 71, 72, 73, 74, 75, 76, 77, 78, 79, 80
                , 81, 82, 83, 84, 85, 86, 87, 88, 89, 90
                , 91, 92, 93, 94, 95, 96, 97, 98, 99, 100

        };
        quickSort.quickSort(arr, 0, arr.length - 1);
        // System.out.println(Arrays.toString(arr2));
    }
}
